P1587 [NOI2016]循环之美

发布于 2020-09-12 | 分类于莫比乌斯反演 | 5分钟 | 764字数

类比十进制下的纯循环小数， $k$ 进制下的纯循环小数满足最简分数分母与 $k$ 互质。

而题目要求相同数值只计数一次，所以只需要考虑最简分数的情况。

那么答案为：

P2480 [SDOI2010]古代猪文

发布于 2020-09-12 | 分类于数论 | 4分钟 | 515字数

g^{\sum_{d|n}C_{n}^{n/d}} \mod 999911659

g^{\sum_{d|n}C_{n}^{d}} \mod 999911659

发布于 2020-09-12 | 分类于最大流、网络流 | 5分钟 | 758字数

网络流24题为了使飞机数量尽量少，一架飞机尽量多飞几趟航班。将航班看成一个点，其实就是求最小路径覆盖。

发布于 2020-09-12 | 分类于数论、欧拉函数 | 2分钟 | 266字数

\sum_{i=1}^n(i,n)

\sum_{d|n}d\sum_{i=1}^n[(i,n)=d]

发布于 2020-09-12 | 分类于数论、莫比乌斯反演 | 6分钟 | 1028字数

因为每回合击中的概率是固定的，所以只需要算一次。概率为：可以击中的情况/总情况。每个点有

(n+1)^2

个位置，所以总情况为

(n+1)^4

发布于 2020-09-12 | 分类于数论 | 3分钟 | 417字数

如果你做过 P4358 [CQOI2016]密钥破解，那么你基本上就凉了。

这道题跟背景没有任何关系。

注意到二元不定方程： $xe1+ye2=(e1,e2)=1$

发布于 2020-09-12 | 分类于树状数组、莫比乌斯反演 | 5分钟 | 758字数

\sum_{i=1}^n\sum_{j=1}^m \sigma((i,j))

\sum_{d=1}^{\min(n,m)}\sigma(d)\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=d]

发布于 2020-09-12 | 分类于数论、欧拉函数 | 1分钟 | 141字数

观察样例可以发现：

发布于 2020-09-12 | 分类于莫比乌斯反演 | 3分钟 | 471字数

这道题的反推还是挺有意思的。

\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor \frac{n}{j} \rfloor}\sum_{q=1}^{\lfloor \frac{n}{j} \rfloor}[(i,j)=1][(p,q)=1]

发布于 2020-09-12 | 分类于树形dp | 4分钟 | 750字数

此题有一个神仙结论：最优链上最多包含一个‘2’，且‘2’不能在链的两边。 至于证明过于简单但很麻烦（~~其实是我懒~~），给大家推荐一个博客，点这。

有了这个结论之后，我们就可以愉快的开始树形dp了。